线性表

1 线性表的定义和基本操作

1.1 线性表的定义

线性表是具有相同数据类型的n(n≧0)个数据元素的有限序列。在线性表中，除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
线性表特点：

• 表中元素个数有限
• 表中元素具有逻辑顺序性
• 每个元素都是数据元素
• 元素的数据类型相同
• 表中元素具有抽象性

1.2 线性表的基本操作

InitList(&L)
Length(L)
LocateElem(L,e)
GetElem(L,i)
ListInsert(&L,i,e)
ListDelect(&L,i,&e)
PrintList(L)
Empty(L)
DestoryList(&L)

2 线性表的顺序表示

2.1 顺序表的定义

线性表的顺序存储称为顺序表，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。
线性表的顺序存储类型描述如下：

#define MaxSize 100
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

上述采用静态分配方式分配内存，也可采用动态分配方式，描述如下：

#define InitSie 100
typedef struct{
    ElemType *data;
    int MaxSie,length;
}SqList;

C语言中动态分配语句为
L.data=(ElemType*)malloca(sizeof(ElemType)*InitSize
C++中的动态分配语句是：
L.data= new ElemType(InitSize)

顺序表的最主要特点是随机访问，即通过首地址和元素序号直接访问元素。

注：顺序表的存储结构是随机存取，而链表的存储结构是顺序存取，注意区分。

2.2 顺序表上基本操作的实现

1. 插入操作
   插入算法的评价时间复杂度为O(n)

   bool ListInsert(SqList &L,int i,ElemType e){
       if(i<=1||i>L.length+1)           //判断i是否越界
           return false;
       if(L.length==MaxSize)            //判断空间是否满
           return false;
       for(int j=L.length;j>=i;j--){    //移动元素
           L.data[j]=L.data[j-1];
       }
       L.data[i-1]=e;                   //插入元素  
       L.length++;
       return true;
   }

2. 删除操作
   删除操作的时间复杂度为O(n)

   bool ListDelect(SqList &L,int i,ElemType &e){
       if(i<1||i>L.length)
           return false;
       e=L.data[i-1];
       for(int j=i-1;j<L.length-1;j++){
           L.data[j]=L.data[j+1];
       }
       L.length--;
       return ture;
   }

3. 顺序查找/按值查找
   在顺序表L中查找第一个元素等于e的元素，并返回其位序。
   顺序查找的时间复杂度为O(n)

   int LocateElem(SqList L,ElemType e){
       int i;
       for(i=0;i<L.length;i++){
           if(L.data[i]==e)
               return i+1;
       }
       return 0;
   }

---

3 线性表的链式表示

3.1 单链表的定义

线性表的链式存储称为单链表，它通过一组任意的存储单元存储线性表中的元素。对每个链表结点有数据域和指针域，数据域存放该元素自身信息，指针域指向后继结点。
单链表的结构类型描述如下

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

单链表中的元素离散地分布在存储空间中，不能直接访问。查找特定结点时，需要从表头开始遍历。依次查找。
头结点： 在单链表的第一个结点之前附加一个节点，称为头结点。
头指针：指向头结点的非空指针

3.2 单链表上基本操作的实现

1. 头插法建立单链表
   算法思想：将新节点插入到头结点之后。
   时间复杂度：O(n)。

   LinkList CreateList(LinkList &L){
       LNode *s;
       L=(LinkList)malloca(sizeof(LinkList));
       int x;
       scanf("%d",&x);
       while(x!=9999){
           s=(LNode)malloca(sizeof(LinkList));
           s->data=x;
           s->next=L->next;
           L->next=s;
           scanf("%d",&x);
       }
       return L;
   }

2. 采用尾插法建立单链表
   算法思想：将新节点插入到表尾，修改表尾指针

   LinkList CreateList(LinkList &L){
       LNode *s;
       L=(LinkList)malloca(sizeof(LinkList));          //为表分配内存
       LNode *r = L;                                   //临时指针r用于指向表尾元素
       int x;
       scanf("%d",&x);
       while(x!=9999){                                 //以x=9999为循环结束标志
           s=(LNode*)malloca(sizeof(LinkList));        //为新节点分配内存
           s->data=x;                                  //
           r->next=s;                                  //连接新节点
           r = s;                                      //修改表尾指针
           scanf("%d",&x);
       }
       r->next = NULL;                                 //表尾的next域为空
       return L;
   }

3. 按序号查找结点值
   算法思想：从头指针开始，顺指针next域逐个往下搜索,找到第i个结点。
   时间复杂度：O(n)。

   LNode *GetElem(LinkList L,int i){
       int count=0;
       LNode *p = L->next;          //找到第一个节点
       if(i==0)                     //若查找第0个节点，返回链表的头结点
           return L;
       if(i<1)                      //越界判断
           return NULL；
       while(count<i&&p){           //边计数边移动指针，找到第i个结点
           p=p->next;
           count++;
       }
       return p;
   }

4. 按值查找表结点
   算法思想：从第一个结点开始，依次比对结点数据域和给定值e，若有相等的返回该结点指针，否则返回NULL。
   时间复杂度：O(n)。

   LNode *LocateElem(LinkList L,ElemType e){
       LNode *p = L->next;             //第一个结点
       while(p!=NULL&&P->data!=e){     //判断结点是否存在后再判断data域是否相等
           p=p->next;
       }
       return p;
   }

5. 结点插入操作
   算法思想：先找到第i-1个结点，再插入新的第i个结点，之后修改指针
   时间复杂度：O(n)。

   void LinkListInsert(LinkList &L,int i,ElemType e){
       LNode *p = GetElem(LinkList L,i-1);    //找到第i-1个结点
       if(p==NULL)                            //判断结点是否存在
           return;
       LNode *s=(LNode*)malloca(sizeof(LNode));  //创建新结点
       s->data = e;
       s->next = p->next
       p->next = s;
       return；
   }

6. 删除结点操作
   算法思想：先找到第i-1个结点，修改其指针域为下下个结点，再释放的i个结点
   时间复杂度：O(n)。

   void LinkListDelect(LinkList &L,int i){
       LNode *p = GetElem(LinkList L,i-1);        //找到第i-1个结点
       if(p==NULL||p->next==NULL)                //若第i-1或的i个结点不存在，直接返回
           return;
       q = p->next;                              //暂存待删除结点
       p->next=p->next->next;
       free(q);                                  //释放存储空间
       return;
   }

2.3 双链表

双链表结点类型描述

typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinklist;

1. 双链表的插入操作
   在双链表中的p指针所指结点后插入新节点*s的代码片段

   s->next = p->next;
   p->next->prior = s;
   p->next =s;
   s->prior =p;

2. 双链表的删除操作

   p->next = q->next;
   q->next->prior = p;
   free(q);

2.4 循坏链表

1. 循环单链表
   循环单链表中的最后一个结点指针指向头结点。
2. 循环双链表
   在循环单链表和双链表基础上，头结点的poior指针指向表尾结点。

2.5 静态链表

静态链表结点包含数据域和指针域，这里的指针是结点的相对地址，静态链表需要预先分配一块连续的内存空间。

2.6 顺序表和链表的比较

	顺序表	链表
存取方式	顺序存取和随机存取	顺序存取
存储方式	逻辑相邻元素物理存储位置也相邻	逻辑相邻元素物理存储位置不一定相邻
操作复杂度	查找、插入和删除：O(n)	查找、插入和删除:O(1)
空间分配	静态存储分配	动态存储分配